1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
| #include<iostream>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<cstring>
using namespace std;
inline int read(){
int x=0,w=0;char c=getchar();
while(!isdigit(c))w|=c=='-',c=getchar();
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return w?-x:x;
}
namespace star
{
const int maxn=3e5+10;
int n,l;
int ecnt,head[maxn],nxt[maxn<<1],to[maxn<<1],dis[maxn<<1];
inline void addedge(int a,int b,int c){
to[++ecnt]=b,nxt[ecnt]=head[a],head[a]=ecnt;dis[ecnt]=c;
to[++ecnt]=a,nxt[ecnt]=head[b],head[b]=ecnt;dis[ecnt]=c;
}
int d[maxn],mx,fa[maxn],diam[maxn],tot,sum;
void dfs1(int x,int f,int &dia){
fa[x]=f;
if(mx<d[x])
mx=d[x],dia=x;
for(int i=head[x];i;i=nxt[i]){
int u=to[i];
if(u==f)continue;
d[u]=d[x]+dis[i];
dfs1(u,x,dia);
}
}
inline void diameter(){
int dia,dia2;
dfs1(1,0,dia);
mx=0;d[dia]=0;
dfs1(dia,0,dia2);
while(dia2!=dia){
diam[++tot]=dia2;
dia2=fa[dia2];
}
diam[++tot]=dia;
}
int h[maxn],dep[maxn],q[maxn],ans=0x3f3f3f3f;
void dfs2(int x,int f){
for(int i=head[x];i;i=nxt[i]){
int u=to[i];
if(u==f)continue;
dfs2(u,x);
dep[x]=max(dep[x],dep[u]+dis[i]);
}
}
inline void solve(){
for(int i=2;i<tot;i++){
int x=diam[i];
h[i]=0;dep[x]=0;
for(int j=head[x];j;j=nxt[j]){
int u=to[j];
if(u==diam[i-1] or u==diam[i+1])continue;
dfs2(u,x);
h[i]=max(h[i],dep[u]+dis[j]);
}
}
int s=1,t=0,ls=0,rt=mx,from=1;
for(int i=1;i<=tot;i++){
while(s<=t and d[diam[from]]-d[diam[i]]>l)from++,s+=(from>q[s]),ls=(mx-d[diam[from]]);
while(s<=t and h[i]>h[q[t]])t--;
q[++t]=i;rt=d[diam[i]];
ans=min(ans,max(h[q[s]],max(ls,rt)));
}
printf("%d",ans);
}
inline void work(){
n=read(),l=read();
for(int a,b,c,i=1;i<n;i++)a=read(),b=read(),c=read(),addedge(a,b,c);
diameter();
solve();
}
}
signed main(){
star::work();
return 0;
}
|
